<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Решение некоторых NP-трудных задач</h2>
<ol>
  <li>Определения</li>
  <ol>
    <li>Классы P и NP</li>
    <li>NP-трудная задача</li>
    <li>NP-полная задача</li>
  </ol></li>
  <li>Классические NP-трудные задачи (формулировки)</li>
  <ol>
    <li>SAT, 3-SAT</li>
    <li>Максимальная клика, независмое множество, минимальное контролирующее множество</li>
    <li>Раскраска вершин графа, ребер графа. В минимальное количество цветов, в 3 цвета</li>
    <li>Разбиение графа на клики</li>
    <li>Поиск гамильтонова пути, цикла, маршрута коммивояжера, самого длинного пути</li>
    <li>Поиск двух непересекающихся путей A-B и C-D</li>
    <li>3-сочетание (аналог для трех дольного графа)</li>
    <li>Проверка графов на изоморфность</li>
  </ol></li>
  <li>SAT</li>
  <ol>
    <li>Жадное решение 2-SAT за O(VE)</li>
    <li>Решение 2-SAT за O(E) черезе компоненты сильной связности</li>
    <li>Решение 3-SAT за O(2<sup>n</sup>m)</li>
    <li>Решение 3-SAT за O(1.71<sup>n</sup>m)</li>
    <li>Решение 3-SAT за O(1.33<sup>n</sup>m)</li>
  </ol></li>
  <li>Клики</li>
  <ol>
    <li>Решение за O(2<sup>n</sup>)</li>
    <li>Решение за O(2<sup>n/2</sup>)</li>
    <li>Решение за O(3<sup>n/3</sup>)</li>
    <li>Решение за O(1.32<sup>n</sup>)</li>
  </ol></li>
  <li>Раскраска вершин в 3 цвета</li>
  <ol>
    <li>Вероятностное решение за O(1.5<sup>n</sup>)</li>
    <li>Решение за O(3<sup>n/3</sup>)</li>
  </ol></li>
  <li>Раскраска ребер в 3 цвета</li>
  <ol>
    <li>Решение за O(2<sup>n</sup>)</li>
    <li>Решение за O(3<sup>n/2</sup>)</li>
    <li>Решение за O(1.44<sup>3n/2</sup>)</li>
  </ol></li>
  <li>Раскраска вершин в минимальное количество цветов</li>
  <ol>
    <li>За O(3<sup>n</sup>)</li>
    <li>За O(2.44<sup>n</sup>m)</li>
    <li>За O<sup>*</sup>(2<sup>n</sup>) (с использованием Фурье!)</li>
  </ol></li>
  <li><span style="color: blue;"><i>Not read </i></span>Гамильтонов путь</li>
  <ol>
    <li><span style="color: blue;"><i>Not read </i></span>За O(2<sup>n</sup>n<sup>2</sup>) с O(2<sup>n</sup>n) памяти</li>
    <li><span style="color: blue;"><i>Not read </i></span>За O(2<sup>n</sup>n<sup>2</sup>) с O(2<sup>n</sup>) памяти</li>
    <li><span style="color: blue;"><i>Not read </i></span>За O(2<sup>n</sup>n<sup>3</sup>) с O(polynom(n)) памяти (формула включения-исключения)</li>
  </ol></li>
</ol>
